#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <unordered_set>
#include <map>

using namespace std;

// 847. 访问所有节点的最短路径
class Solution1
{
public:
    int shortestPathLength(vector<vector<int>>& graph) 
    {
        int n = graph.size();
        // 初始化队列及标记数组，存入起点
        queue<tuple<int, int, int>> q; // index, mask, dist
        vector<vector<bool>> visited(n, vector<bool>(1 << n)); // 节点编号及当前状态
        for(int i = 0; i < n; ++i)
        {
            q.push({i, 1 << i, 0});
            visited[i][1 << i] = 0;
        }

        while(!q.empty())
        {
            auto [cur, mask, dist] = q.front();
            q.pop();

            // 找到答案，返回结果
            if(mask == (1 << n) - 1) return dist;

            for(int x : graph[cur])
            {
                int nextMask = mask | (1 << x);
                if(!visited[x][nextMask])
                {
                    q.push({x, nextMask, dist + 1});
                    visited[x][nextMask] = true;
                }
            }
        }
        return 0;
    }
};

// 834. 树中距离之和
class Solution2
{
public:
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) 
    {
        vector<vector<int>> g(n); // g[x] 表示 x 的所有邻居
        for(auto& e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        vector<int> ret(n);
        vector<int> size(n, 1);
        function<void(int, int, int)> dfs = [&](int x, int fa, int depth)
        {
            ret[0] += depth; // depth 是 0 到 x 的距离
            for(int y : g[x]) // 遍历 x 的邻居 y
            {
                if(y != fa) // 避免访问父节点
                {
                    dfs(y, x, depth + 1);
                    size[x] += size[y];
                }
            }
        };
        dfs(0, -1, 0); // 0 没有父节点

        function<void(int, int)> reroot = [&](int x, int fa)
        {
            for(int y : g[x]) // 遍历 x 的邻居 y
            {
                if(y != fa) // 避免访问父节点
                {
                    ret[y] = ret[x] + n - 2 * size[y];
                    reroot(y, x); // x 是 y 的父节点
                }
            }
        };
        reroot(0, -1);

        return ret;
    }
};

// 310. 最小高度树
class Solution3
{
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) 
    {
        if(n == 1) return {0};

        vector<int> inDegree(n);
        vector<vector<int>> g(n);
        for(auto& e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
            ++inDegree[x];
            ++inDegree[y];
        }

        vector<int> ret;
        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            if(inDegree[i] == 1) q.push(i);
        }

        int remainNodes = n;
        while(remainNodes > 2)
        {
            int sz = q.size();
            remainNodes -= sz;
            for(int i = 0; i < sz; ++i)
            {
                int cur = q.front();
                q.pop();
                for(int v : g[cur])
                {
                    if(--inDegree[v] == 1)
                    {
                        q.push(v);
                    }
                }
            }
        }

        while(!q.empty())
        {
            ret.push_back(q.front());
            q.pop();
        }
        return ret;
    }
};

// 2581. 统计可能的树根数目
class Solution4
{
public:
    int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses, int k) 
    {
        vector<vector<int>> g(edges.size() + 1);
        for(auto& e : edges)
        {
            int x = e[0];
            int y = e[1];
            g[x].push_back(y);
            g[y].push_back(x); // 据图
        }    

        unordered_set<long> s;
        for(auto& e : guesses) // guesser 转成哈希表
        {
            s.insert((long) e[0] << 32 | e[1]); // 两个 4 字节数压缩成一个 8 字节数
        }

        int ret = 0, cnt0 = 0;
        function<void(int, int)> dfs = [&](int x, int fa)
        {
            for(int y : g[x])
            {
                if(y != fa)
                {
                    cnt0 += s.count((long)x << 32 | y); // 以 0 为根时，猜对了
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);

        function<void(int, int, int)> reroot = [&](int x, int fa, int cnt)
        {
            ret += cnt >= k; // 此时 cnt 就是以 x 为根时的猜对次数
            for(int y : g[x])
            {
                if(y != fa)
                {
                    reroot(y, x, cnt - s.count((long)x << 32 | y) // 原来是对的，现在错了
                                     + s.count((long)y << 32 | x)); // 原来是错的，现在对了
                }
            }
        };
        reroot(0, -1, cnt0);
        return ret;
    }
};

// 851. 喧闹和富有
class Solution5
{
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) 
    {
        int n = quiet.size();
        vector<vector<int>> g(n);
        vector<int> inDeg(n);
        for(auto& r : richer)
        {
            g[r[0]].push_back(r[1]);
            ++inDeg[r[1]];
        }

        vector<int> ret(n);
        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            ret[i] = i;
            if(inDeg[i] == 0)
            {
                q.push(i);
            }
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(int y : g[x]) // x > y
            {
                if(quiet[ret[x]] < quiet[ret[y]])
                {
                    ret[y] = ret[x];
                }
                if(--inDeg[y] == 0) // 比 y 有钱的人少了一个
                {
                    q.push(y);
                }
            }
        }

        return ret;
    }
};

// 886. 可能的二分法
class Solution6
{
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) 
    {
        vector<int> ufs(n + 1, -1);
        vector<vector<int>> g(n + 1);
        for(auto& d : dislikes)
        {
            g[d[0]].push_back(d[1]);
            g[d[1]].push_back(d[0]);
        }

        function<int(int)> Find = [&](int x)
        {
            return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
        };

        function<bool(int, int)> Same = [&](int x, int y)
        {
            return Find(x) == Find(y);
        };

        function<void(int, int)> Union = [&](int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if(x == y) return;
            if(abs(ufs[x]) < abs(ufs[y])) swap(x, y);   
            ufs[x] += ufs[y];
            ufs[y] = x;
        };  

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j < g[i].size(); ++j)
            {
                Union(g[i][0], g[i][j]);
                if(Same(i, g[i][j])) return false;
            }
        }
        return true;
    }
};

// 1109. 航班预订统计
class Solution7
{
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) 
    {
        vector<int> ret(n);
        for(auto& b : bookings)
        {
            ret[b[0] - 1] += b[2];
            if(b[1] < n) ret[b[1]] -= b[2];
        }

        for(int i = 1; i < n; ++i)
        {
            ret[i] += ret[i - 1];
        }
        return ret;
    }
};

// 1094. 拼车
class Solution8
{
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) 
    {
        int diff[1001] = {0};
        for(auto& t : trips)
        {
            int num = t[0], from = t[1], to = t[2];
            diff[from] += num;
            diff[to] -= num;
        }

        int sum = 0;
        for(int x : diff)
        {
            sum += x;
            if(sum > capacity) return false;
        }
        return true;
    }
};

// 2406. 将区间分为最少组数
class Solution9
{
public:
    int minGroups(vector<vector<int>>& intervals) 
    {
        map<int, int> diff;
        for(auto& p : intervals)
        {
            ++diff[p[0]];
            --diff[p[1] + 1];
        }
        
        int ret = 0, sum = 0;
        for(auto& [_, d] : diff)
        {
            ret = max(ret, sum += d);
        }
        return ret;
    }
};
